package _17_剑指Offer;

public class _53_剑指OfferII中缺失的数字 {

    public static void main(String[] args) {

        _53_剑指OfferII中缺失的数字 v = new _53_剑指OfferII中缺失的数字();
//        int[] ins = new int[]{0, 1, 2, 3, 4, 5, 6, 7, 9};
        int[] ins = new int[]{0};
        System.out.println(v.missingNumber(ins));

    }


    public int missingNumber(int[] nums) {
        int begin = 0;
        int end = nums.length - 1;
        // 找到最后一个元素
        while (begin <= end) {
            int mid = begin + end >> 1;
            // 不存在nums[mid] < mid的情况
            if (nums[mid] > mid) {
                // 缺失元素在左边
                end = mid - 1;
            } else if (nums[mid] == mid) {
                // 缺失元素在右边
                begin = mid + 1;
            }
        }
        return begin;
    }

}
